/*
 * @Author: szx
 * @Date: 2022-02-11 12:27:03
 * @LastEditTime: 2022-02-11 12:54:16
 * @Description:
 * @FilePath: \leetcode\900-999\912\912_mergeSort.js
 */

// const mergeSort = (nums, left = 0, right = nums.length - 1, res) => {
//     if (left >= right) return;
//     const mid = Math.floor((left + right) / 2);
//     mergeSort(nums, left, mid, res);
//     mergeSort(nums, mid + 1, right, res);
//     merge(nums, left, right, res);
// };
// // merge就是整合两个已经排序完的数组，分别是[left,mid]和[mid+1,right]
// const merge = (nums, left, right, res) => {
//     const mid = Math.floor((left + right) / 2);
//     let i = left,
//         j = mid + 1,
//         k = 0;
//     while (i <= mid && j <= right) {
//         if (nums[i] <= nums[j]) res[k++] = nums[i++];
//         else res[k++] = nums[j++];
//     }
//     while (i <= mid) res[k++] = nums[i++];
//     while (j <= right) res[k++] = nums[j++];
//     for (let i = left; i <= right; i++) nums[i] = res[i - left];
// };

// var sortArray = function (nums) {
//     const n = nums.length;
//     const res = new Array(n).fill(0);
//     mergeSort(nums, 0, n - 1, res);
//     return nums;
// };


var sortArray = function (nums) {
    const n = nums.length;
    const res = new Array(n).fill(0);
    const mergeSort = (nums, left = 0, right = nums.length - 1) => {
        if (left >= right) return;
        const mid = Math.floor((left + right) / 2);
        mergeSort(nums, left, mid, res);
        mergeSort(nums, mid + 1, right, res);
        let i = left,
            j = mid + 1,
            k = 0;
        while (i <= mid && j <= right) {
            if (nums[i] <= nums[j]) res[k++] = nums[i++];
            else res[k++] = nums[j++];
        }
        while (i <= mid) res[k++] = nums[i++];
        while (j <= right) res[k++] = nums[j++];
        for (let i = left; i <= right; i++) nums[i] = res[i - left];
    };
    mergeSort(nums);
    return nums;
};
console.log(sortArray([4, 5, 2, 1, 3]));
